Obeleži sve kategorije koje odgovaraju problemu

Библиотечке функције за рад са низовима

У овом поглављу ћемо приказати решења заснована на употреби библиотечких колекција (низова, листи, вектора и сл.) и функција. Нагласимо да се већина задатака из овог поглавља може решити и без употребе колекција. Иако је програмски кôд таквих решења обично дужи, она су свакако меморијски ефикаснија. Такође, таква решења се могу сматрати илустративнијим, јер се кроз њих изучавају веома важни, фундаментални алгоритми. Са друге стране, у неким ситуацијама у програмирању ћемо елементе морати сместити у низ или ћемо их из неког разлога већ имати у том облику. Тада се применом библиотечких функција могу добити веома кратка и елеганта решења. Библиотечке функције ћемо у овом поглављу приказати кроз веома једноставне задатке у којима њихова примена не мора да буде оптималан избор.

Библиотечке функције у језику C++ су дизајниране тако да се могу примењивати над различитим колекцијама података (статичким и динамичким низовима, векторима, листама и слично). Колекција (или неки њен део тј. опсег узастопних елемената) задају се итераторима. Итератори се најчешће користе у пару и ограничавају опсег узастопних елемената колекције тако што први итератор указује на почетни елемент тог опсега, а други указује непосредно иза последњег елемента опсега.

Неке од најчешће коришћених функција декларисане у заглављу <iterator> су:

• begin, end – враћају итераторе који ограничавају опсег датог низа, вектора и слично. Функција begin враћа итератор који указује на први елемент, а end враћа итератор који указује непосредно иза последњег елемента (на пример begin(v) враћа итератор који указује на почетак вектора v). Многе колекције подржавају и методе begin и end (на пример, v.begin() враћа итератор који указује на почетак вектора v). Име низа је могуће употребити као итератор који указује на почетак низа;
• distance – враћа растојање (број елемената) у опсегу ограниченом са два итератора која се прослеђују као аргументи функције (први итератор показује на почетак тј. на први елемент опсега, а други непосредно иза краја тј. последњег елемента опсега). На пример, ако је it итератор који указује на неки елемент унутар вектора v, тада се његов индекс може одредити помоћу distance(begin(v), it);
• next, prev – враћа итератор који показује на елемент дате колекције који је испред тј. иза прослеђеног итератора, на датом растојању; ако се као други аргумент не проследи растојање, подразумевано се тражи итератор на наредни тј. претходни елемент колекције. На пример, next(begin(v)) је итератор који указује на други елемент вектора v (ако такав постоји), док је prev(end(a), 2) итератор који указује на претпоследњи елемент низа a (ако такав постоји).
• Над итераторима се могу примењивати и аритметичке операције: it + n одговара итератору који се добија када се итератор it помери надесно n пута (исто као и next(it, n)). На пример, ако низ a има n елемената тада се његов опсег може задати итераторима a и a+n. Разлика два итератора одређује број елемената између њих (укључујући први и не укључујући последњи (исто као и функција distance).

Неке од најчешће коришћених функција декларисане у заглављу <algorithm> су:

• min_element и max_element – враћа итератор на елемент са најмањом тј. највећом вредношћу у опсегу задатом помоћу два дата итератора; као трећи аргумент се функцији може проследити и функција која врши поређење два елемента (подразумевано се користи поређење оператором <);
• transform – пресликавају се сви елементи из опсега задатог помоћу два итератора; као трећи аргумент се прослеђује итератор на почетак колекције у коју се резултат смешта, а као четврти функција (најчешће анонимна) којом се елементи пресликавају;
• count – враћа број појављивања елемента у опсегу задатом помоћу два итератора;
• copy_if – колекција се филтрира тако што се копирају они елементи из опсега задатог помоћу два итератора који задовољавају услов који се испитује функцијом која се задаје као последњи аргумент функције copy_if (та функција прима елемент колекције и враћа true ако он треба да буде копиран); филтрирани елементи смештају се у колекцију чији се итератор почетка прослеђује функцији copy_if као њен трећи аргумент и подразумева се да је она алоцирана тако да може да прихвати све елементе који се копирају. Ако број тих елемената није унапред познат, могуће је проследити back_inserter(it) где је it итератор који указује на почетак неалоцираног вектора (тада се приликом копирања елементи у вектор убацују помоћу push_back).
• remove, remove_if – колекција се филтрира тако што се из ње уклањају они елементи из опсега задатог помоћу два итератора који задовољавају неки услов; у случају функције remove задаје се вредност и уклањају се сви елементи једнаки тој вредности, док се у случају функције remove_if услов испитује функцијом која се задаје као последњи аргумент функције remove_if (та функција прима елемент колекције и враћа true ако он треба да буде обрисан); преостали елементи се премештају на почетак оригиналне колекције, а функција remove_if враћа итератор непосредно иза последњег задржаног елемента; након уклањања елемената, колекција се често скраћује функцијом erase;
• erase – брише елемент из колекције задат итератором или опсег колекције задат помоћу два итератора;
• any_of, all_of – проверава да ли неки елемент тј. да ли сви елементи опсега задатог помоћу два итератора задовољавају услов који се проверава bool функцијом која се задаје као трећи аргумент функције any_of; функција any_of тј. all_of такође враћа вредност типа bool;
• find, find_if – враћа итератор који показује на прво појављивање елемента која се тражи у опсегу задатом помоћу два итератора; ако се елемент не јавља у овом опсегу елемената враћа се итератор који показује на позицију иза краја датог опсега; функција find прима вредност која се тражи, док функција find_if прима функцију која проверава да ли текући елемент има захтевано својство и проналази први елемент који то својство задовољава.
• equal – проверава да ли су два опсега једнака; као аргументе прима итераторе који ограничавају први опсег и итератор који показује на почетак другог опсега;
• reverse – обрће редослед елемената опсега задатог помоћу два итератора.
• sort – сортира елементе опсега задатог помоћу два итератора. Они се подразумевано пореде оператором <, а могуће је као трећи аргумент функцији sort проследити и функцију којом ће се два елемента поредити (она треба да врати true ако и само ако први треба да се нађе испред другога у сортираном редоследу).

У неким примерима ћемо користити и наредне функције декларисане у заглављу <numeric>:

• iota – попуњава елементе колекције (низа или вектора) из датог опсега задатог помоћу два итератора узастопним бројевима почев од вредности коју наводимо као трећи аргумент функције;
  
• accumulate – рачуна збир елемената у опсегу задатом помоћу два итератора; као трећи параметар наводи се иницијална вредност збира – најчешће је то 0 или 0.0 у зависности од типа елемената који се сабирају. Функција accumulate израчунава збир тако што обрађује један по један елемент опсега у сваком кораку текућу вредност збира сабира са текућим елементом опсега. То се може променити ако се као четврти аргумент функције accumulate зада функција која прихвата досадашњу акумулирану вредност и текући елемент опсега и која описује како се нова акумулирана вредност добија на основу њих (та функција треба да врати нову вредност).

Библиотечке функције за рад са низовима

У овом поглављу ћемо приказати решења заснована на употреби библиотечких колекција (низова, листи, вектора и сл.) и функција. Нагласимо да се већина задатака из овог поглавља може решити и без употребе колекција. Иако је програмски кôд таквих решења обично дужи, она су свакако меморијски ефикаснија. Такође, таква решења се могу сматрати илустративнијим, јер се кроз њих изучавају веома важни, фундаментални алгоритми. Са друге стране, у неким ситуацијама у програмирању ћемо елементе морати сместити у низ или ћемо их из неког разлога већ имати у том облику. Тада се применом библиотечких функција могу добити веома кратка и елеганта решења. Библиотечке функције ћемо у овом поглављу приказати кроз веома једноставне задатке у којима њихова примена не мора да буде оптималан избор.

Библиотека Linq проширује језик C# додавањем функционалности коje омогућавају једноставно издвајање и обраду елемената неке серије података. Да би она могла да се користе, неопходно је на почетку програма навести директиву using System.Linq.

Набројиве колекције. Као што смо видели, серије података се представљају низовима и листама (али и другим библиотечким колекцијама, које нису представљене у овој збирци). И ниске се могу схватити као серије карактера који их сачињавају. За све ове колекције је заједничко да омогућавају да се елементи колекције наброје, редом од првог до последњег, коришћењем петље foreach. Такве колекције називају се набројиве колекције (прецизније, све оне имплементирају интерфејс IEnumerable<T>, где је T тип елемената колекције). Посебна врста набројиве колекције је енумератор (њега можемо чувати у променљивој декларисаног типа IEnumerable<T>). Као и кроз све друге набројиве колекције и кроз енумератор се може итерирати петљом foreach и на њега се могу примењивати све методе библиотеке Linq. Специфичност енумератора је то да његови елементи нису истовремено складиштени у меморији (они се генеришу само по потреби, током итерације, и зато такве колекције називамо лењим). Енумератор се, ако је то потребно, може претворити у низ методом ToArray или у листу методом ToList (тада се они складиште у меморију и на њих се могу примењивати и функционалности специфичне за низове тј. листе).

Изградња енумератора правилних серија. Функција Enumerable.Range гради серију узастопних бројева. Параметри су јој први елемент серије и број елемената (на пример, Enumerable.Range(3, 5) гради серију бројева 3, 4, 5, 6, 7). Резултат се добија у облику енумератора. Функција Enumerable.Repeat гради серију дате дужине у којој је сваки елемент једнак датом броју (на пример, Enumerable.Repeat(2, 3) гради серију бројева 2, 2, 2). Резултат се добија у облику енумератора.

Укључивање библиотеке Linq, све набројиве колекције проширује мноштвом корисних метода, које имплементирају основне алгоритме (које смо раније ручно имплементирали). Прикажимо неке од њих.

Елементарне статистике. Често је у задатку потребно одредити основне статистике неке колекције (минимум, максимум, збир, просечну вредност). Библиотека Linq располаже одговарајућим методама, те минимални елемент можемо наћи методом Min, максимални елемент методом Max, збир свих елемената колекције методом Sum, a њихов просек методом Average.

var min = a.Min();
var max = a.Max();
var zbir = a.Sum();
var prosek = a.Average();

Број елемената у било којој колекцији можемо добити методом Count. Она се може применити на било коју набројиву колекцију, али може бити неефикасна (димензију низа је много брже очитати својством Length, а листе својством Count).

var br = a.Count();

Агрегација.

Методом Aggregate се може остварити израчунавање различитих статистика за које не постоје методе које их директно израчунавају. Сви елементи колекције се агрегирају применом неке бинарне операције. Резултат се иницијализује на први елемент колекције, а затим се у наредним корацима обрађује један по један елемент колекције, кренувши од другог. У сваком кораку се резултат ажурира применом наведене операције на текућу вредност резултата и на текући елемент који се обрађује. Операција се најчешће наводи у облику ламбда-израза облика (acc, x) => f(acc, x), где је acc текућа (тренутно акумулирана) вредност резултата, а x текући елемент који се агрегира. На овај начин могуће је рецимо могуће одредити производ елемената колекције a.

int proizvod = a.Aggregate((acc, x) => acc * x);

Пресликавање. Понекад је потребно извршити пресликавање елемената неке колекције и надаље у задатку радити са тако добијеним вредностима. Методом Select се сви елементи полазне колекције пресликавају применом функције наведене као параметар (то је најчешће неки ламбда-израз облика x => f(x)). Као резултат се добија енумератор (који се, ако је потребно, може претворити у низ или листу). На пример, наредним позивом методе Select израчунава се листа која садржи квадрате вредности полазног низа а.

var kvadrati = a.Select(x => x * x).ToList();

Често је потребно израчунати збир елемената пресликане колекције. Зато је омогућено да метода Sum прими као аргумент функцију којом се серија пресликава пре израчунавања збира (слично важи и за функције Min, Max и Average). Дакле, ако желимо да одредимо збир квадрата вредности колекције a, уместо:

var kvadrati = a.Select(x => x*x);
int sumaKvadrata = kvadrati.Sum();

можемо искористити наредни позив:

int sumaKvadrata = a.Sum(x => x*x);

Приметимо да у првом случају није било потребно резултат пресликавања преводити у низ или листу, јер се метод Sum може спровести и на енумератору добијеном методом Select, чији елементи нису истовремено смештени у меморију.

Филтрирање. Често је потребно да филтрирамо неку колекцију и да издвојимо само оне њене елементе који задовољавају неки услов. Mетода Where се може применити на низ или на листу и служи за филтрирање елемената који задовољавају дато својство, које је наведено као аргумент. И у овом случају се резултат враћа у облику енумератора. На пример, ако желимо да издвојимо само позитивне елементе низа a то можемо урадити следећим кодом:

var pozitivni = a.Where(x => x > 0);

Претрага.

Метода Contains проверава да ли се дати елемент налази у колекцији.

string[] razred = {"Ana", "Marko", "Milan", "Jelena"};
string ucenik = Console.ReadLine();
if (razred.Contains(ucenik))
  Console.WriteLine("Ucenik se nalazi u razredu");

Методе Any и All проверавају да ли неки тј. да ли сви елементи колекције задовољавају дато својство. Својство се наводи као аргумент ових метода (често у облику ламбда израза). Помоћу ових функција бисмо, на пример, могли да проверимо да ли су сви елементи низа a позитивни, а у случају да нису да ли је бар неки елемент низа позитиван.

if (a.All(x => x > 0))
  Console.WriteLine("svi elementi su pozitivni");
else if (a.Any(x => x > 0))
  Console.WriteLine("postoji pozitivni element");
else Console.WriteLine("ne postoji pozitivni element");

Поређење колекција. Методом Enumerable.SequenceEqual се може испитати једнакост две колекције (подсетимо се, поређење помоћу оператора == само ће упоредити меморијске адресе на којима се те колекције налазе, а не и њихове елементе).

if (Enumerable.SequenceEqual(a, b))
  Console.WriteLine("nizovi su jednaki");

Префикси и суфикси. Метода Take враћа префикс жељене дужине дате колекције, док се методом Skip израчунава њен суфикс који се добија изостављањем првих неколико елемената. У оба случаја резултат је енумератор. На пример, ако желимо да издвојимо и да изоставимо прва три елемента дате колекције, то можемо урадити на следећи начин:

var prvaTri = a.Take(3);
var bezPrvaTri = a.Skip(3);